#define _CRT_SECURE_NO_WARNINGS 1
const int N = 5e4 + 10;
int f[N][21];
int d[N];
void dfs(int u, int fa, vector<vector<int>>& e) {
    d[u] = d[fa] + 1;
    f[u][0] = fa;

    for (int i = 1; i <= 20; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }

    for (auto it : e[u]) {
        if (it != fa) {
            dfs(it, u, e);
        }
    }

}
class TreeAncestor {
public:
    TreeAncestor(int n, vector<int>& parent) {
        memset(f, 0, sizeof f);
        memset(d, 0, sizeof d);
        e.resize(n + 1);
        //int n=parent.size();
        for (int i = 0; i < n; i++) {
            e[parent[i] + 1].push_back(i + 1);
        }

        dfs(1, 0, e);
        //     for(int i=1;i<=n;i++){
        //     cout<<d[i]<<endl;
        //    }
    }

    int getKthAncestor(int node, int k) {
        int u = node + 1;
        for (int i = 20; i >= 0; i--) {
            if (d[f[u][i]] >= d[node + 1] - k) {
                u = f[u][i];
            }
        }
        return u - 1;
    }
    vector<vector<int>> e;

};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */